use std::mem;
use std::ptr;

type ArrayListValue = *mut libc::c_void;
type ArrayListEqualFunc = extern "C" fn(value1: ArrayListValue, value2: ArrayListValue) -> libc::c_int;
type ArrayListCompareFunc = extern "C" fn(value1: ArrayListValue, value2: ArrayListValue) -> libc::c_int;

#[repr(C)]
pub struct ArrayList {
    pub data: *mut ArrayListValue,
    pub length: libc::c_uint,
    pub _alloced: libc::c_uint,
}

impl ArrayList {
    pub fn new(length: libc::c_uint) -> *mut ArrayList {
        let mut new_arraylist = unsafe { libc::malloc(mem::size_of::<ArrayList>()) as *mut ArrayList };
        if new_arraylist.is_null() {
            return ptr::null_mut();
        }

        let alloced = if length > 0 { length } else { 16 };
        unsafe {
            new_arraylist.as_mut().unwrap()._alloced = alloced;
            new_arraylist.as_mut().unwrap().length = 0;

            new_arraylist.as_mut().unwrap().data = unsafe { libc::malloc(alloced as usize * mem::size_of::<ArrayListValue>()) as *mut ArrayListValue };
            if new_arraylist.as_mut().unwrap().data.is_null() {
                unsafe { libc::free(new_arraylist as *mut libc::c_void) };
                return ptr::null_mut();
            }
        }

        new_arraylist
    }

    pub fn free(arraylist: *mut ArrayList) {
        if !arraylist.is_null() {
            unsafe {
                libc::free(arraylist.as_mut().unwrap().data as *mut libc::c_void);
                libc::free(arraylist as *mut libc::c_void);
            }
        }
    }

    pub fn enlarge(&mut self) -> bool {
        let newsize = self._alloced * 2;
        let data = unsafe { libc::realloc(self.data as *mut libc::c_void, newsize as usize * mem::size_of::<ArrayListValue>()) as *mut ArrayListValue };
        if data.is_null() {
            false
        } else {
            self.data = data;
            self._alloced = newsize;
            true
        }
    }

    pub fn insert(&mut self, index: libc::c_uint, data: ArrayListValue) -> bool {
        if index > self.length {
            return false;
        }

        if self.length + 1 > self._alloced {
            if !self.enlarge() {
                return false;
            }
        }

        unsafe {
            ptr::copy(self.data.offset(index as isize), self.data.offset(index as isize + 1), (self.length - index) as usize);
        }
        unsafe { self.data.offset(index as isize).write(data) };
        self.length += 1;

        true
    }

    pub fn append(&mut self, data: ArrayListValue) -> bool {
        self.insert(self.length, data)
    }

    pub fn prepend(&mut self, data: ArrayListValue) -> bool {
        self.insert(0, data)
    }

    pub fn remove_range(&mut self, index: libc::c_uint, length: libc::c_uint) {
        if index > self.length || index + length > self.length {
            return;
        }

        unsafe {
            ptr::copy(self.data.offset(index as isize + length as isize), self.data.offset(index as isize), (self.length - (index + length)) as usize);
        }
        self.length -= length;
    }

    pub fn remove(&mut self, index: libc::c_uint) {
        self.remove_range(index, 1);
    }

    pub fn index_of(&self, callback: ArrayListEqualFunc, data: ArrayListValue) -> libc::c_int {
        for i in 0..self.length {
            if callback(unsafe { self.data.offset(i as isize).read() }, data) != 0 {
                return i as libc::c_int;
            }
        }
        -1
    }

    pub fn clear(&mut self) {
        self.length = 0;
    }

    pub fn sort(&mut self, compare_func: ArrayListCompareFunc) {
        unsafe {
            arraylist_sort_internal(self.data, self.length, compare_func);
        }
    }
}

unsafe extern "C" fn arraylist_sort_internal(list_data: *mut ArrayListValue, list_length: libc::c_uint, compare_func: ArrayListCompareFunc) {  
    if list_length <= 1 {
        return;
    }

    let pivot = list_data.offset((list_length - 1) as isize).read();
    let mut list1_length = 0;

    for i in 0..list_length - 1 {
        let value = list_data.offset(i as isize).read();
        if compare_func(value, pivot) < 0 {
            let tmp = list_data.offset(i as isize).read();
            list_data.offset(i as isize).write(list_data.offset(list1_length as isize).read());
            list_data.offset(list1_length as isize).write(tmp);
            list1_length += 1;
        }
    }

    let list2_length = list_length - list1_length - 1;
    list_data.offset((list_length - 1) as isize).write(list_data.offset(list1_length as isize).read());
    list_data.offset(list1_length as isize).write(pivot);

    arraylist_sort_internal(list_data, list1_length, compare_func);
    arraylist_sort_internal(list_data.offset((list1_length + 1) as isize), list2_length, compare_func);
}